package com.leetcode.algs4.search;

/**
 * @author Dennis Li
 * @date 2020/6/16 11:26
 */
public class LinearProbingHashST<Key, Value> {
    private int N;
    private int M = 16;
    private Key[] keys;
    private Value[] vals;

    public LinearProbingHashST(int capacity) {
        M = capacity;
        N = 0;
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    private void resize(int capacity) {
        LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(capacity);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], vals[i]);
            }
        }
        keys = temp.keys;
        vals = temp.vals;
        M = temp.M;
    }

    public void put(Key key, Value val) {
        // 数组加倍
        if (N >= M / 2) resize(2 * M);

        int i;
        // 计算散列值，如果不为空，一直进行探测
        for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
            // 找到key，进行赋值
            if (keys[i].equals(key)) {
                vals[i] = val;
                return;
            }
        }
        // 为空，则将值赋给新值
        keys[i] = key;
        vals[i] = val;
        // 总数加一
        N++;
    }

    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                return vals[i];
        return null;
    }

    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }

    public void delete(Key key) {
        if (!contains(key)) return;
        int i = hash(key);
        while (!key.equals(keys[i]))
            i = (i + 1) % M;
        keys[i] = null;
        vals[i] = null;
        i = (i + 1) % M;
        // 调整右侧所有元素
        while (keys[i] != null) {
            // 临时存储
            Key keyToRedo = keys[i];
            Value valToRedo = vals[i];
            // 移除
            keys[i] = null;
            vals[i] = null;
            // 这里N--,在put方法中又会++
            N--;
            // 探测插入
            put(keyToRedo, valToRedo);
            i = (i + 1) % M;
        }
        // 删除完成N--
        N--;
        // 如果N<M/8，将数组缩容
        if (N > 0 && N == M / 8) resize(M / 2);
    }

}
